Conventionally, apparatuses that transmit and receive data in wireless communication networks for mobile phones, or apparatuses that transmit and receive data such as internet protocol (IP) packets in computer networks determine whether a packet length is a multiple of a certain number, so as to confirm that the received data is normal. In this way, the apparatuses check the packet length of a fixed-length or variable-length packet.
In such wireless communication networks for mobile phones and computer networks, a maximum real-time processing is required for communication. Thus, it is critical how to check the packet length at high speed.
For example, Japanese Laid-open Patent Publication Nos. 2002-14805 and 2003-15864 disclose multiple determining circuits that determine whether a given operand represented by binary digits is an integral multiple of an operation value represented by 2n−1 (n is a natural number. In the latter publication, the operand is 5). Such multiple determining circuits divide the operand into n-bit units, sum up them, and use a sum value as a new operand. The multiple determining circuits then repeat such dividing and summing until a bit array corresponding to the sum value becomes equal to or less than a predetermined bit number, and determine whether the bit array for the sum value being equal to or less than the predetermined bit number for the first time is contained in integer multiples of an operation value stored in advance. In this way, it is determined whether the given operand is the operation value.
Japanese Laid-open Patent Publication No. 10-187037 proposes a prime number determination method that determines the primality of an element belonging to a group C, made up of integers B being different from an integer A or integers being different from an integer A by a multiple of an integer B. Calculation is performed using the integer B or a multiple of the integer B as a dividend and one or more integers as a divisor or a group of divisors, and a remainder or a group of remainders are stored. From the group of the remainders thus stored, a remainder corresponding to an element of the group C is used, and calculation is performed using the element of the group C as a dividend and one or more integers as a divisor(s), and a remainder(s) are found. In this way, the primality of the element belonging to the group C is determined. By applying this method, whether the element of the group C is a prime number or a composite number is found, and whether the element of the group C is a multiple of a certain number is determined.
U.S. Pat. No. 4,949,294 discloses a method including finding a remainder from composite numbers with a modulus of mi=4K+3 (k is an integer satisfying k>0), assigning indices for each composite number and its remainder, respectively, and storing the indices. A remainder found from a multiple of two composite numbers is a sum of remainders that are found by performing the above-described calculation with the respective composite numbers. Thus, it is possible to find composite numbers corresponding to a sum of such remainders by using a relationship between indices stored in advance. In this way, complex multiplication can be performed at high speed. By applying this method, whether an integer A is a multiple of an integer B is determined by trying and finding an integer α satisfying A=αB.
Conventional technologies typically seen in Japanese Laid-open Patent Publication Nos. 2002-14805 and 2003-15864 impose a processing load due to repetitive processes including dividing the operand into n-bit units and summing up obtained values until a sum value becomes equal to or less than a predetermined bit number. In addition, information needs to be prepared in advance as a reference for determining whether a sum value, found by dividing the operand into n-bit units and summing up obtained values, is a multiple of the operation value when the sum value becomes equal to or less than a predetermined bit number for the first time.
In a conventional technology typically seen in Japanese Laid-open Patent Publication No. 10-187037, it is required to calculate and store in advance a remainder or a group of remainders that are found when one or more integers are used as a divisor or a group of divisors. Further, this technology places the focus on generating a prime number that is hardly found the primality, and does not concern quick processing for finding a remainder(s) produced by the division of an element belonging to the group C (dividend) by one or more integers (divisor), by using the element corresponding to one of the residues in the stored group.
In a conventional technology typically seen in U.S. Pat. No. 4,949,294, whether an integer A is a multiple of an integer B is determined by trying and finding α satisfying A=αB. This may require enormous processing time for determining whether the integer A is a multiple of the integer B.